import type { StringMatcher } from '../definitions.js';

// Source: https://github.com/ka-weihe/fastest-levenshtein/blob/master/mod.ts
// License: https://github.com/ka-weihe/fastest-levenshtein/blob/master/LICENSE.md
export class LevenshteinStringMatcher implements StringMatcher {
	readonly #peq = new Uint32Array(0x10000);

	#myers_32(a: string, b: string): number {
		const n = a.length;
		const m = b.length;
		const lst = 1 << (n - 1);
		let pv = -1;
		let mv = 0;
		let sc = n;
		let i = n;
		while (i--) {
			this.#peq[a.charCodeAt(i)] |= 1 << i;
		}
		for (i = 0; i < m; i++) {
			let eq = this.#peq[b.charCodeAt(i)];
			const xv = eq | mv;
			eq |= ((eq & pv) + pv) ^ pv;
			mv |= ~(eq | pv);
			pv &= eq;
			if (mv & lst) {
				sc++;
			}
			if (pv & lst) {
				sc--;
			}
			mv = (mv << 1) | 1;
			pv = (pv << 1) | ~(xv | mv);
			mv &= xv;
		}
		i = n;
		while (i--) {
			this.#peq[a.charCodeAt(i)] = 0;
		}
		return sc;
	}

	#myers_x(b: string, a: string): number {
		const n = a.length;
		const m = b.length;
		const mhc = [];
		const phc = [];
		const hsize = Math.ceil(n / 32);
		const vsize = Math.ceil(m / 32);
		for (let i = 0; i < hsize; i++) {
			phc[i] = -1;
			mhc[i] = 0;
		}
		let j = 0;
		for (; j < vsize - 1; j++) {
			let mv = 0;
			let pv = -1;
			const start = j * 32;
			const vlen = Math.min(32, m) + start;
			for (let k = start; k < vlen; k++) {
				this.#peq[b.charCodeAt(k)] |= 1 << k;
			}
			for (let i = 0; i < n; i++) {
				const eq = this.#peq[a.charCodeAt(i)];
				const pb = (phc[(i / 32) | 0] >>> i) & 1;
				const mb = (mhc[(i / 32) | 0] >>> i) & 1;
				const xv = eq | mv;
				const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb;
				let ph = mv | ~(xh | pv);
				let mh = pv & xh;
				if ((ph >>> 31) ^ pb) {
					phc[(i / 32) | 0] ^= 1 << i;
				}
				if ((mh >>> 31) ^ mb) {
					mhc[(i / 32) | 0] ^= 1 << i;
				}
				ph = (ph << 1) | pb;
				mh = (mh << 1) | mb;
				pv = mh | ~(xv | ph);
				mv = ph & xv;
			}
			for (let k = start; k < vlen; k++) {
				this.#peq[b.charCodeAt(k)] = 0;
			}
		}
		let mv = 0;
		let pv = -1;
		const start = j * 32;
		const vlen = Math.min(32, m - start) + start;
		for (let k = start; k < vlen; k++) {
			this.#peq[b.charCodeAt(k)] |= 1 << k;
		}
		let score = m;
		for (let i = 0; i < n; i++) {
			const eq = this.#peq[a.charCodeAt(i)];
			const pb = (phc[(i / 32) | 0] >>> i) & 1;
			const mb = (mhc[(i / 32) | 0] >>> i) & 1;
			const xv = eq | mv;
			const xh = ((((eq | mb) & pv) + pv) ^ pv) | eq | mb;
			let ph = mv | ~(xh | pv);
			let mh = pv & xh;
			score += (ph >>> (m - 1)) & 1;
			score -= (mh >>> (m - 1)) & 1;
			if ((ph >>> 31) ^ pb) {
				phc[(i / 32) | 0] ^= 1 << i;
			}
			if ((mh >>> 31) ^ mb) {
				mhc[(i / 32) | 0] ^= 1 << i;
			}
			ph = (ph << 1) | pb;
			mh = (mh << 1) | mb;
			pv = mh | ~(xv | ph);
			mv = ph & xv;
		}
		for (let k = start; k < vlen; k++) {
			this.#peq[b.charCodeAt(k)] = 0;
		}
		return score;
	}

	#distance(a: string, b: string): number {
		if (a.length < b.length) {
			const tmp = b;
			b = a;
			a = tmp;
		}
		if (b.length === 0) {
			return a.length;
		}
		if (a.length <= 32) {
			return this.#myers_32(a, b);
		}
		return this.#myers_x(a, b);
	}

	#closest(str: string, arr: readonly string[]): string {
		let min_distance = Infinity;
		let min_index = 0;
		for (let i = 0; i < arr.length; i++) {
			const dist = this.#distance(str, arr[i]);
			if (dist < min_distance) {
				min_distance = dist;
				min_index = i;
			}
		}
		return arr[min_index];
	}

	getClosestMatch(target: string, candidates: Array<string>): string {
		return this.#closest(target, candidates);
	}
}
